a. Field of the Invention
The instant invention relates to surface modeling. In particular, the instant invention relates to a system and method for repairing a triangulated mesh model of a three dimensional surface.
b. Background Art
It is well known to generate a heart chamber geometry in preparation for cardiac diagnostic or therapeutic procedures. Often, a mapping catheter is introduced into the heart chamber of interest and moved around within the heart chamber, either randomly, pseudo-randomly, or according to one or more preset patterns. The three-dimensional coordinates of the mapping catheter are measured using a localization system (sometimes also referred to as a “mapping system,” “navigation system,” or “positional feedback system”). The three-dimensional coordinates become a geometry point (or “location data point”). Multiple measurements may be taken as the catheter is moved within the heart chamber, resulting in a cloud of geometry points that defines the geometry of the heart chamber.
Various surface construction algorithms may be utilized to wrap a surface around the cloud of geometry points to obtain a surface representation of the heart chamber geometry. One such surface construction algorithm generates a convex hull about the cloud of geometry points. The convex hull may be generated using standard algorithms such as the Qhull algorithm. The Qhull algorithm is described in Barber, C. G., Dobkin, D. P., and Huhdanpaa, H. T., “The Quickhull algorithm for convex hulls,” ACM Trans. on Mathematical Software, 22(4):469-483 (December 1996). Other algorithms used to compute a convex hull shape are also known.
Another surface construction algorithm is Alpha Shapes. The alpha shape is a generalization of the convex hull and a subgraph of the Delaunay triangulation. For a sufficiently large alpha, the alpha shape is identical to the convex hull, while for a sufficiently small alpha, the alpha shape is just the set of geometry points themselves. Intermediate values of alpha produce surfaces that reconstruct the model of the heart chamber to various levels of detail.
Still another exemplary method for creating a shell corresponding to the shape of the heart chamber fits a radial array of bins around groups of geometry points. The bins are typically constructed by determining a mean center point of the cloud of geometry points and extending borders radially outward from the mean center point to the furthest geometry point within the slice encompassed by the bin. The radial end faces of the bins thus approximate the surface of the heart chamber wall. Common graphic shading algorithms can then be employed to “smooth” the surface of the shell thus created out of the radial end faces of the bins.
Typically, these surface construction algorithms result in a surface modeled by a mesh of triangular facets—that is, a list of (x, y, z) coordinates for each vertex and another list of (i, j, k) indices into the first list describing which vertices are connected to form each triangle of the mesh. If the surface is closed, it is desirable for the mesh to be “watertight,” meaning that every edge of every triangular facet is shared by exactly one other triangular facet. It is also desirable that the mesh be “manifold,” which imposes the additional requirement that any two edges sharing a vertex can be reached from each other by stepping across a unique sequence of triangles sharing edges with each other and that vertex—in other words, that no two distinct parts of the mesh “touch” each other at a single vertex.
In actual practice, however, triangulated surface meshes are not always both watertight and manifold. For instance, joining or merging two triangulated surface meshes into a single triangulated surface mesh may leave gaps, duplicate vertices, duplicate facets, holes, or other problems near the region or regions where they intersect. Unfortunately, these problems may interfere with subsequent processing algorithms that assume or require meshes to be both watertight and manifold.